package HeuNavigation;


import javax.imageio.ImageIO;
import javax.swing.*;
import java.awt.*;
import java.io.File;
import java.io.IOException;
import java.text.SimpleDateFormat;
import java.util.Comparator;
import java.util.Date;
import java.util.LinkedList;
import java.util.Scanner;

public class HeuMap {
    static private LinkedList<Node> NodeList; //节点链表，存储节点
    static private int totalNode; //总节点个数
    static public int[][] dis;//用邻接矩阵存储距离
    static private int[][] path;//记录最短路径
    static int max=10000;//用来表示不互通

    //根据学校内的信息初始化节点，并加入到链表中
    static public void init_List(){
        totalNode=12;
        NodeList=new LinkedList<>();
        NodeList.add(new Node(0,"校医院",'E'));
        NodeList.add(new Node(1,"五公寓",'B'));
        NodeList.add(new Node(2,"十六公寓",'B'));
        NodeList.add(new Node(3,"南体育场",'D'));
        NodeList.add(new Node(4,"小美",'C'));
        NodeList.add(new Node(5,"逸夫楼",'A'));
        NodeList.add(new Node(6,"图书馆",'A'));
        NodeList.add(new Node(7,"21B",'A'));
        NodeList.add(new Node(8,"大美",'C'));
        NodeList.add(new Node(9,"七公寓",'B'));
        NodeList.add(new Node(10,"体育馆",'D'));
        NodeList.add(new Node(11,"北体育场",'D'));
    }

    //初始化距离矩阵
    static public void init_dis(){
        dis= new int[][]{
                {0,7,max,5,max,6,max,max,max,max,max,max},
                {7,0,5,4,8,max,max,max,max,max,max,max},
                {max,5,0,max,10,max,16,max,max,max,max,max},
                {5,4,max,0,5,8,max,max,max,max,max,max},
                {max,8,10,5,0,max,6,max,6,max,max,max,max},
                {6,max,max,8,max,0,max,8,max,5,max,max},
                {max,max,15,max,6,max,0,max,8,max,max,10},
                {max,max,max,max,max,8,max,0,4,5,max,7},
                {max,max,max,max,6,max,8,4,0,max,max,10},
                {max,max,max,max,max,4,max,5,max,0,10,max},
                {max,max,max,max,max,max,max,max,max,10,0,15},
                {max,max,max,max,max,max,max,7,10,max,15,0}
        };

        //初始化path并将元素都置为-1
        path=new int[totalNode][totalNode];
        for (int i=0;i<totalNode;i++){
            for (int j=0;j<totalNode;j++){
                path[i][j]=-1;
            }
        }
    }

    //随机初始化人流量
    static void init_peopleNum(LinkedList nodeList){
        for (int i=0;i<totalNode;i++){
            Node temp=(Node)nodeList.get(i);
            int random_num=(int)(Math.random()*100)+1;
            temp.setPeopleNum(random_num);
        }
    }

    //利用floyd求多源最短路径
    static public void init(){
        //初始化链表和矩阵和人流量
        init_List();
        init_dis();
        init_peopleNum(NodeList);

        //floyd
        for (int k=0;k<totalNode;k++){

            for (int i=0;i<totalNode;i++){

                for (int j=0;j<totalNode;j++){

                    if(dis[i][j]>dis[i][k]+dis[k][j])
                    {
                        dis[i][j]=dis[i][k]+dis[k][j];	//距离矩阵
                        path[i][j]=k;		//路径矩阵
                    }

                }
            }

        }
    }

    //输出距离矩阵
    public static void show_dis(){
        for (int i=0;i<12;i++){
            for (int j=0;j<12;j++){
                System.out.print(dis[i][j]+" ");
            }
            System.out.println();
        }
    }

    //输出路径矩阵
    public static void show_path(){
        for (int i=0;i<12;i++){
            for (int j=0;j<12;j++){
                System.out.print(dis[i][j]+" ");
            }
            System.out.println();
        }
    }

    //显示地图
    public static void show_map(){
        //利用io操作读取自定义的学校地图并显示出来
        Image image = null;
        try {
            String name;
            File sourceimage = new File("/Users/ytcslaptop/IdeaProjects/DataStructure/src/HeuNavigation/map.jpeg");//可能会出现空指针异常，出现了就换成绝对路径
            image = ImageIO.read(sourceimage);
        } catch (IOException e) {
            System.out.println("找不到地图图片文件！");
        }

        JFrame frame = new JFrame();

        JLabel label = new JLabel(new ImageIcon(image));

        frame.getContentPane().add(label, BorderLayout.CENTER);

        frame.pack();

        frame.setVisible(true);

        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);


    }

    //显示所有节点
    static public void show_list(){
        for (int i=0;i<totalNode;i++){
            System.out.println(NodeList.get(i).toString());
        }
    }

    //根据index获取名称
    static String getName(int index){
        return NodeList.get(index).getName();
    }

    //根据name获取index
    static int getIndex(String name){
        for (int i=0;i<totalNode;i++){
            Node temp=NodeList.get(i);
            if (name.equals(temp.getName()))
                return temp.getIndex();
        }
        return -1;
    }
    //获取附近地点，即获取最近的三个附近位置
    static void getNearBy(){
        String name="";
        Scanner s=new Scanner(System.in);
        System.out.println("请输入你所在的地点");
        name=s.next();
        int index=getIndex(name);
        if (index==-1){
            System.out.println("名称有误，请重试！");
             return;
        }
        int[] in=new int[totalNode];
        for (int i=0;i<totalNode;i++){
            in[i]=i;
        }
        int[] t=new int[totalNode];
        for (int i=0;i<totalNode;i++){
            t[i]=dis[index][i];
        }
        for (int i=0;i<totalNode;i++){
            for (int j=i+1;j<totalNode;j++){
                if (t[i]>t[j]){
                    //swap
                    int temp=t[i];
                    t[i]=t[j];
                    t[j]=temp;
                    temp=in[i];
                    in[i]=in[j];
                    in[j]=temp;
                }
            }
        }
        //输出最近的三个地点
        System.out.println(name+"附近最近的三个地点为：");
        //因为0的位置存贮的是自己的信息，所以从1开始计算
        System.out.println(getName(in[1])+":"+t[1]+"00m");
        System.out.println(getName(in[2])+":"+t[2]+"00m");
        System.out.println(getName(in[3])+":"+t[3]+"00m");
    }

    //输出最短距离所对应的路径
    static void shortest_path_show(int i,int j){
        if (path[i][j]>=0)
            shortest_path_show(i,path[i][j]);
        System.out.print("-->"+getName(j));
    }

    //求最短路径并输出路线
    static void shortest_path(){
        Scanner s=new Scanner(System.in);
        int a;
        int b;
        System.out.println("输入当前地点：");
        a=getIndex(s.next());
        while (true){
            System.out.println("输入目的地点：");
            b=getIndex(s.next());
            if (a==b){
                System.out.println("出发地不允许和目的地重复！请重新输入！");
                continue;
            }else {
                System.out.println("路线：");
                System.out.print(getName(a));
                shortest_path_show(a,b);
                System.out.println();
                System.out.println("最短距离："+dis[a][b]+"00m");
                return;
            }
        }

    }

    //按场合查询
    static void selectByType(){
        System.out.println("请输入你要去的场合");
        System.out.println("1:图书馆/教室");
        System.out.println("2:学生公寓");
        System.out.println("3：食堂");
        System.out.println("4：体育馆");
        System.out.println("5：医院");
        int k;
        Scanner s=new Scanner(System.in);
        k=s.nextInt();
        int a;
        System.out.println("输入您的当前位置");
        a= getIndex(s.next());
        switch (k){
            case 1:select(a,'A');
                    break;
            case 2:select(a,'B');
                    break;
            case 3:select(a,'C');
                    break;
            case 4:select(a,'D');
                    break;
            case 5:select(a,'E');
                    break;
        }
    }

    //根据传入的index，选择最近的目标场所并输出
    static void select(int a,char c){
        if (NodeList.get(a).getType()==c){
            System.out.println("你已在目标场所，无需移动！");
            return;
        }
        int min=999;
        int index=-1;
        for (int i=0;i<totalNode;i++){
            if (NodeList.get(i).getType()==c&&dis[a][i]<min){
                min=dis[a][i];
                index=i;
            }
        }
        if (index==-1){
            System.out.println("不能从该位置到达！");
        }else {
            System.out.println("距离你最近的目标场所是："+getName(index));
        }
    }

    //地点距离排序
    static void dis_sort(){
        System.out.println("输入你目前所在地点");
        Scanner s=new Scanner(System.in);
        int a=getIndex(s.next());
        int[] arr=new int[totalNode];
        for (int i=0;i<totalNode;i++){
            arr[i]=dis[a][i];
        }
        int[] in=new int[totalNode];
        for (int i=0;i<totalNode;i++){
            in[i]=i;
        }
        for (int i=0;i<totalNode;i++){
            for (int j=i+1;j<totalNode;j++){
                if (arr[i]>arr[j]){
                    int temp=arr[i];
                    arr[i]=arr[j];
                    arr[j]=temp;
                    temp=in[i];
                    in[i]=in[j];
                    in[j]=temp;
                }
            }
        }
        System.out.println("各个地点按距离从小到近排序为：");
        for (int i=1;i<totalNode;i++){
            System.out.print(getName(in[i])+" ");
        }
        System.out.println();
        System.out.println("-------------------------");
    }

    //查询第n小的地点
    static void select_fixedDis(){
        System.out.println("输入你想查询的出发地：");
        Scanner s=new Scanner(System.in);
        int a=getIndex(s.next());
        int[] temp=new int[totalNode];
        for (int i=0;i<totalNode;i++){
            temp[i]=dis[a][i];
        }
        System.out.println("请输入N的值");
        int k=s.nextInt();
        int res=randomizedselect(temp,0,totalNode-1,k);
        for (int i=0;i<totalNode;i++){
            if (dis[a][i]==res){
                System.out.println("该位置为："+getName(i));
                System.out.println("距离为："+res+"00m");
                break;
            }
        }
    }

    //实现查询数组中第n个小的元素
    static public int randomizedselect(int[] arr,int p,int r,int k){
        if (p==r)
            return arr[p];
        int i=randomizedPartition(arr,p,r);
        int j=i-p+1;
        if (k<=j)
            return randomizedselect(arr,p,i,k);
        else
            return randomizedselect(arr,i+1,r,k-j);
    }

    static public int randomizedPartition(int[] arr,int p,int r){
        int i=(int)(Math.random()*(r-p)+p);
        int temp=arr[i];
        arr[i]=arr[p];
        arr[p]=temp;
        return partition(arr,p,r);
    }

    static public int partition(int[] arr,int p,int r){
        int i=p;
        int j=r+1;
        int x=arr[p];
        while (true){
            while (arr[++i]<x&&i<r);
            while (arr[--j]>x);
            if (i>=j)
                break;
            int temp=arr[i];
            arr[i]=arr[j];
            arr[j]=temp;
        }
        arr[p]=arr[j];
        arr[j]=x;
        return j;
    }

    //人流量更新查询
    static void select_peopleNum(){

        for (int i=0;i<totalNode;i++){
            Node temp=(Node)NodeList.get(i);
            int random_num=(int)(Math.random()*100)+1;
            temp.setPeopleNum(random_num);
        }

        LinkedList temp=new LinkedList<Node>();
        temp=NodeList;

        temp.sort(new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {
                return o1.getPeopleNum()>o2.getPeopleNum()?1:-1;
            }
        });

        //获取当前时间
        SimpleDateFormat sdf = new SimpleDateFormat();
        sdf.applyPattern("yyyy-MM-dd HH:mm:ss a");
        Date date = new Date();
        System.out.print("更新后按人流量由高到低的排序结果为");
        System.out.println("        当前时间："+sdf.format(date));
        for (int i=0;i<totalNode;i++){
            System.out.println(temp.get(i).toString());
        }
    }
}
